//
//  Tree.swift
//  DataStructureAndAlgorithm
//
//  Created by icemelon on 2021/8/8.
//

import Foundation


//二叉树基类
class BinaryTree<T: Comparable> {
    class Node<T: Comparable> : CustomStringConvertible, Equatable {
        
        static func == (lhs: Node<T>, rhs: Node<T>) -> Bool {
            return lhs.element == rhs.element
        }
        
        var element: T
        var parent: Node? = nil
        var right: Node? = nil
        var left: Node? = nil
        
        var height: Int = 1 //avl树使用 也可以使用一个新avlnode继承node
        
        init(element: T, parent: Node?) {
            self.element = element
            self.parent = parent
        }
        
        convenience init(element: T) {
            self.init(element: element, parent: nil)
        }
        
        var description: String {
            return "\(element)"
        }
    }
    
    var root: Node<T>?
    
    var size: Int = 0
    
    func isEmpty() -> Bool {
        return size == 0
    }
}

//为了搜索树使用 也可以在搜索树中使用filePrivate修饰
extension BinaryTree.Node {
    func isLeft() -> Bool {
        return self.element == self.parent?.left?.element
    }
    
    func isRight() -> Bool {
        return self.element == self.parent?.right?.element
    }
    
    func isRoot() -> Bool {
        return self.parent == nil
    }
    //度 为 2
    func hasTwoChildren() -> Bool {
        return self.left != nil && self.right != nil
    }
    //度 为 1
    func hasSingleChild() -> Bool {
        return self.left != nil || self.right != nil
    }
    //度 为 0  叶子节点
    func hasNoChild() -> Bool {
        return self.left == nil && self.right == nil
    }
    
    //获取前驱节点  既中序遍历的前一个节点
    func predecessor() -> BinaryTree.Node<T>? {
        var pre = self.left
        while pre != nil {
            if pre?.right != nil {
                pre = pre?.right
            }
            else {
                return pre
            }
        }
        return pre
    }
    //获取后继节点  既中序遍历的后一个节点
    func succcessor() -> BinaryTree.Node<T>? {
        var pre = self.right
        while pre != nil {
            if pre?.left != nil {
                pre = pre?.left
            }
            else {
                return pre
            }
        }
        return pre
    }
}

//avl
extension BinaryTree.Node {
    
    var leftHeight: Int {
        get {
            return self.left != nil ? self.left!.height : 0
        }
    }
    
    var rightHeight: Int {
        get {
            return self.right != nil ? self.right!.height : 0
        }
    }
    
    var tallerChild: BinaryTree.Node<T> {
        get {
            return leftHeight >= rightHeight ? self.left! : self.right!
        }
    }
    
    var balanceFactor: Int { //左子树的高度减去右子树的高度
        get {
            return leftHeight - rightHeight
        }
    }
    
    func isBalance() -> Bool {
        return abs(self.balanceFactor) <= 1
    }
    
    func updateHeight() { //更新高度为左右子树的最大高度
        let maxHeight = leftHeight >= rightHeight ? leftHeight : rightHeight
        self.height = maxHeight + 1
    }
    
    
}
